bf2c70e164a4a2beec01191ad28ae9e5608b87f0,java/src/KdTreeRectQuery.java,KdTreeRectQuery,randomizedPartition,#Point[]#number#number#boolean#,71
Before Change
static final Random rnd = new Random(1);
static int randomizedPartition(Point[] a, int low, int high, boolean divX) {
swap(a, low + rnd.nextInt(high - low), high - 1);
int v = divX ? a[high - 1].x : a[high - 1].y;
int i = low - 1;
for (int j = low; j < high; j++)
if (divX ? a[j].x <= v : a[j].y <= v)
swap(a, ++i, j);
return i;
}
After Change
}
}
static int partition(Point[] a, int fromInclusive, int toExclusive, int separatorIndex, boolean divX) {
int i = fromInclusive;
int j = toExclusive - 1;
if (i >= j) return j;
double separator = divX ? a[separatorIndex].x : a[separatorIndex].y;
swap(a, i++, separatorIndex);
while (i <= j) {
while (i <= j && (divX ? a[i].x : a[i].y) < separator)
++i;
while (i <= j && (divX ? a[j].x : a[j].y) > separator)
--j;
if (i >= j)
break;
swap(a, i++, j--);
}
swap(a, j, fromInclusive);
return j;